# 下标统一从1开始
N = int(input())
a = [[0] * (N + 1)]
dp = [[0] * (N + 1) for i in range(N + 1)]
for i in range(N):
    a.append([0] + list(map(int, input().split())))
# dp[i][j]表示是从(i,j)出发到底部的最大值
# （i,j）可以走到（i,j+1）或者（i+1，j+1）

# dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]

# # 更新时需要从下往上更新：从N到1
# for i in range(N,0,-1):
#     # 枚举第i行的每一个位置
#     for j in range(1,i+1):
#         if i==N:
#             dp[i][j]=a[i][j]
#         else:
#             dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j]
#
# print(dp[1][1])
# print(a)

# 从上到下
for i in range(1, N + 1):
    for j in range(1, i + 1):
        if j == 1:
            dp[i][j] = dp[i - 1][j] + a[i][j]
        elif i == j:
            dp[i][j] = dp[i - 1][j - 1] + a[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j]

print(max(dp[N]))

# n种花，每种花的数量不超过a[i],总共摆放m盆，有多少方案
n, m = map(int, input().split())
a = list(map(int, input().split()))
# dp[i][j]表示前i种花，选择出j盆的方案数
dp = [[0] * (m + 1) for i in range(n + 1)]

for i in range(n + 1):
    dp[i][0] = 1
# 如何利用先前的dp[0]...dp[i-1]
# 来求出dp[i][j]
# 考虑当下第i种花的选择：
# 第i种花选择0盆：dp[i-1][j]
# 第i种花选择1盆：dp[i-1][j-1]
# 第i种花选择2盆：dp[i-1][j-2]
# ...
# 第i种花选择a[i]盆：dp[i-1][j-a[i]]
for i in range(1, n + 1):
    for j in range(m + 1):
        # 枚举第i种花选择k盆
        for k in range(min(a[i], j) + 1):
            dp[i][j] += dp[i - 1][j - k]
            dp[i][j] %= 10000007
print(dp[n][m])
